package QuestionDaily;

import java.util.*;

public class maximumSum_2342 {
    /**
     * 请你选出两个下标 i 和 j（i != j）
     * 且 nums[i] 的数位和 与  nums[j] 的数位和相等。
     * 找出并返回 nums[i] + nums[j] 可以得到的 最大值 。
     * @param nums 元素都是 正 整数，下标从 0 开始
     * @return
     */
    public int maximumSum(int[] nums) {
        /**
         * 思路很简单，存储具有相同数位和的数字即可
         * 105ms，太慢了
         */
        int maxSum=-1;
        HashMap<Integer, List<Integer>>map=new HashMap<>(); //存储所有数位和，以及对应的坐标的数字值
        for (int i=0;i<nums.length;i++){
            int mumSum=mumSum(nums[i]);
            if(map.containsKey(mumSum)){  //已经包含了这个数位和，直接对相应的集合添加数值
                map.get(mumSum).add(nums[i]);
            }else {
                List<Integer>list=new ArrayList<>();
                list.add(nums[i]);
                map.put(mumSum,list);
            }
        }
        for (int key:map.keySet()){
            if(map.get(key).size()==1)
                continue;
            Collections.sort(map.get(key),
                    ( i , j )-> j-i
                    ); //对集合降序排序
            maxSum=Integer.max(maxSum,map.get(key).get(0)+map.get(key).get(1));
        }
        return maxSum;
    }

    public int maximumSum2(int[] nums) {
        /**
         * 改进，使用map存储具有相同数位和的数字，并且实时记录对应数字和对应的最大的数字
         */
        int maxSum=-1,num=0;
        HashMap<Integer, Integer>map=new HashMap<>(); //存储数位和，以及对应的最大数字
        for (int i=0;i<nums.length;i++){
            //计算当前数字的数位和
            int mumSum = 0;
            for (int x = nums[i]; x > 0; x /= 10) {
                mumSum += x % 10;
            }
            if(map.containsKey(mumSum)){  //已经包含了这个数位和
                num=map.get(mumSum);//之前存储的最大数字
                maxSum=Integer.max(maxSum,map.get(mumSum)+nums[i]);  //更新最大和
                if(nums[i]>num){  //维护对应数字和的最大数字
                    map.put(mumSum,nums[i]);
                }
            }else {
                map.put(mumSum,nums[i]);
            }
        }
        return maxSum;
    }
    /**
     * 计算数位和
     */
    int mumSum(int num){
        int sum=0;
        while (num!=0){
            sum+=num%10;
            num/=10;
        }
        return sum;
    }

    /**
     *高赞解法,和我基本差别不大，不过可能采用数组
     * @param nums
     * @return
     */
    public int maximumSum3(int[] nums) {
        int ans = -1;
        int[] mx = new int[82]; // 至多 9 个 9 相加
        for (int num : nums) {
            int s = 0; // num 的数位和
            for (int x = num; x > 0; x /= 10) { // 枚举 num 的每个数位
                s += x % 10;
            }
            if (mx[s] > 0) { // 说明左边也有数位和等于 s 的元素
                ans = Math.max(ans, mx[s] + num); // 更新答案的最大值
            }
            mx[s] = Math.max(mx[s], num); // 维护数位和等于 s 的最大元素
        }
        return ans;

    }


}
